
// 打家劫舍1：一排房子，相邻的房屋装有相互连通的防盗系统
// 所以要求不能闯入相邻的房子

int rob(int* nums, int numsSize){
    int i, dp[numsSize+1];  //dp[i] 表示抢前i个房子(不包括i)的最高金额
    dp[0] = 0; dp[1] = nums[0];
    for (i = 1; i < numsSize; i++) {
        // 不抢i房子，dp[i]; 抢i房子，则不能抢i-1房子
        // 如dp[2] = max(dp[1], dp[0]+nums[i]);
        dp[i+1] = fmax(dp[i], dp[i-1]+nums[i]);
    }
    return dp[numsSize];
}


// 打家劫舍2：房子连成环，不能偷相邻的房子
int rob1(int* nums, int start, int end){
    int prev, pprev, cur;
    prev = pprev = 0;
    for (int i = start; i < end; i++) {
        cur = fmax(prev, pprev+nums[i]);
        pprev = prev;
        prev = cur;
    }
    return cur;
}

int rob(int* nums, int numsSize){
    if (numsSize == 0) return 0;
    if (numsSize == 1) return nums[0];
    // 由题意知，第一个房子和最后一个房子相连，分两种情况讨论
    int res1 = rob1(nums, 0, numsSize-1);   //不打抢最后一个房子
    int res2 = rob1(nums, 1, numsSize);     //不打抢第一个房子
    return (res1 > res2)? res1:res2;
}
